package main

func main() {
	
}

//给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
//
// 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
//
// 示例:
//
// X X X X
//X O O X
//X X O X
//X O X X
//
//
// 运行你的函数后，矩阵变为：
//
// X X X X
//X X X X
//X X X X
//X O X X
//
//
// 解释:
//
// 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被
//填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
// Related Topics 深度优先搜索 广度优先搜索 并查集
// 👍 290 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
var n, m int
func solve(board [][]byte)  {
	if len(board) <= 2 || len(board[0]) <= 2 {
		return
	}
	n, m = len(board), len(board[0])
	for i := 0; i < n; i++ {
		dfs(board, i, 0)
		dfs(board, i, m - 1)
	}
	for i := 0; i < m; i++ {
		dfs(board, 0, i)
		dfs(board, n - 1, i)
	}
	for i, bytes := range board {
		for j, b := range bytes {
			if b == 'A' {
				board[i][j] = 'O'
			}
			if b == 'O' {
				board[i][j] = 'X'
			}
		}
	}
}

func dfs(board [][]byte, x, y int) {
	if x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O' {
		return
	}

	board[x][y] = 'A'
	dfs(board, x , y - 1)
	dfs(board, x , y + 1)
	dfs(board, x - 1 , y)
	dfs(board, x + 1 , y)
}
//leetcode submit region end(Prohibit modification and deletion)
